﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution
{
public:
    bool check(vector<int>& s, vector<int>& a_t, string& t)
    {
        int i = 0;
        for (i = 0; i < t.size(); i++)
        {
            if (a_t[t[i] - 'a'] > s[t[i] - 'a'])
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t)
    {
        if (s.size() < t.size())
        {
            return string();
        }

        vector<int> a_s(26, 0), a_t(26, 0);
        int i = 0;
        for (i = 0; i < t.size(); i++)//会有大小写问题
        {
            a_s[s[i] - 'a']++;
            a_t[t[i] - 'a']++;
        }

        int left = 0, right = i - 1;
        int min = INT_MAX;
        string ret;
        while (left <= right && right < s.size())
        {
            if (check(a_s, a_t, t))
            {
                int len = right - left + 1;
                if (len < min)
                {
                    ret.clear();
                    int k = left;
                    while (k <= right)
                    {
                        ret.push_back(s[k]);
                        k++;
                    }
                    min = len;
                    if (min = t.size())
                    {
                        return ret;
                    }
                }
                a_s[s[left] - 'a']--;
                left++;
                continue;
            }
            right++;
            if (right < s.size())
            {
                a_s[s[right] - 'a']++;
            }
        }
        return ret;
    }

    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
        for (auto& s : words) hash1[s]++;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) // 执⾏ len 次
        {
            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size();
                right += len)
            {
                // 进窗⼝ + 维护 count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                {
                    count++;
                }
                // 判断
                if (right - left + 1 > len * m)
                {
                    // 出窗⼝ + 维护 count
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                    {
                        count--;
                    }
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m)
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }

    int search(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target)
            {
                return mid;
            }
            else if (num > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return -1;
    }

    vector<int> searchRange(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int mid = (left + right) / 2;
        while (left <= right)
        {
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid - 1;
            }
            else
            {
                break;
            }
            mid = (left + right) / 2;
        }
        if (nums[mid] != target)
        {
            return vector<int>(-1, -1);
        }
        else
        {
            left = mid, right = mid;
            while (left >= 0 && nums[left] == target)
            {
                left--;
            }
            while (right < nums.size() && nums[right] == target)
            {
                right++;
            }
            return vector<int>(left + 1, right - 1);
        }
    }
};

int main()
{
    Solution S;
    S.minWindow("ADOBECODEBANC", "ABC");

    return 0;
}